SuperHack/SuperHack CD.bin/CODING/CPP/BTREE.ZIP/BTREEIMP.H

C/C++ Source or Header | 1994-11-14 | 20.3 KB | 1,038 lines

/*
 * BTreeImp.h                   B+ Tree Implimentation
 *
 * (c) DownEast Technology, Inc., 1994
 * Written by Steve Nutt
 */

#if !defined(BTREEIMP_H)
#define BTREEIMP_H

#if !defined(BNODE_H)
#include "BNode.h"
#endif
//#define _DEBUG_B_TREE_

template <class Node, class T> class TBPlusTreeIteratorBase;

template <class Node, class T> class TBPlusTreeBase
{
    friend TBPlusTreeIteratorBase <Node, T>;

protected:
    typedef Node::TChain TChain;

public:
    typedef void (*IterFunc) (T&, void*);
    typedef int (*CondFunc) (const T&, void*);
    typedef int (*CompFunc) (const T&, void*);

    TBPlusTreeBase (void)
        {
        root = 0;
        itemCnt = 0;
        }

    unsigned GetItemsInContainer (void) const
        {
        return itemCnt;
        }

    int HasMember (const T* t) const
        {
        return FindNode (t) != 0;
        }

    int IsEmpty (void) const
        {
        return GetItemsInContainer() == 0;
        }

    T* Last (void) const
        {
        return (root ? static_cast<Node*> (root->WalkRight())->DataPtr() : 0);
        }

    T* First (void) const
        {
        return (root ? static_cast<Node*> (root->WalkLeft())->DataPtr() : 0);
        }

    T* Find (const T* t) const
        {
        Node* node = FindNode (t);
        return (node ? node->DataPtr() : 0);
        }

    void Flush (void)
        {
        root = 0;
        itemCnt = 0;
        }

    void ForEach (IterFunc, void*);
    T* LastThat (CondFunc, void*) const;
    T* FirstThat (CondFunc, void*) const;
    T* Search (CompFunc, void*) const;

protected:
    int AddNode (Node*, TChain&);
    void DetachNode (Node*, TChain&);
    Node* FindNode (const T*) const;
    Node* FindNode (const T*, TChain&);

    Node::TNodeBase* root;

private:
    void BalanceAdd (TChain&);
    unsigned itemCnt;

#if __DEBUG > 0
#if defined(_DEBUG_B_TREE_)
    void CheckValues (Node&, const T*&, const T*&);
protected:
    int CheckTree (void);
#endif
#endif
};

/*
 * Member function for template TBPlusTreeBase
 */
template <class Node, class T>
void TBPlusTreeBase<Node, T>::ForEach (
    IterFunc iter,
    void* args)
{
    if (!root)
        return;

    TChain chain;
    chain.Push (&root);
    root->WalkLeft (chain);
    while (!chain.IsEmpty())
    {
        Node& node = *static_cast<Node*> (*chain.Top());
        iter (*node.DataPtr(), args);
        Node::Next (chain);
    }
    chain.Flush (TShouldDelete::NoDelete);
}

template <class Node, class T>
T* TBPlusTreeBase<Node, T>::LastThat (
    CondFunc cond,
    void* args) const
{
    if (!root)
        return 0;

    TChain chain;
    chain.Push (const_cast<Node::TNodeBase**> (&root));
    root->WalkRight (chain);
    T* data;
    while (!chain.IsEmpty())
    {
        data = static_cast<Node*> (*chain.Top())->DataPtr();
        if (cond (*data, args))
            break;

        Node::Previous (chain);
    }
    if (chain.IsEmpty())
        data = 0;

    chain.Flush (TShouldDelete::NoDelete);
    return data;
}

template <class Node, class T>
T* TBPlusTreeBase<Node, T>::FirstThat (
    CondFunc cond,
    void* args) const
{
    if (!root)
        return 0;

    TChain chain;
    chain.Push (const_cast<Node::TNodeBase**> (&root));
    root->WalkLeft (chain);
    T* data;
    while (!chain.IsEmpty())
    {
        data = static_cast<Node*> (*chain.Top())->DataPtr();
        if (cond (*data, args))
            break;

        Node::Next (chain);
    }
    if (chain.IsEmpty())
        data = 0;

    chain.Flush (TShouldDelete::NoDelete);
    return data;
}

template <class Node, class T>
T* TBPlusTreeBase<Node, T>::Search (
    CompFunc compare,
    void* args) const
{
    Node::TNodeBase* node = root;
    while (node)
    {
        T* data = static_cast<Node*> (node)->DataPtr();
        int c = compare (*data, args);
        if (c == 0)
            return data;

        node = c < 0 ? node->Left() : node->Right();
    }
    return 0;
}

template <class Node, class T>
int TBPlusTreeBase<Node, T>::AddNode (
    Node* newNode,
    TChain& chain)
{
#if defined(_DEBUG_B_TREE_)
    CHECK (CheckTree());
#endif

    if (root)
    {
        Node* parent = static_cast<Node*> (*chain.Top());
        if (*newNode->DataPtr() < *parent->DataPtr())
        {
            parent->Left() = newNode;
            chain.Push (&parent->Left());
        }
        else
        {
            parent->Right() = newNode;
            chain.Push (&parent->Right());
        }
        BalanceAdd (chain);
    }
    else
        root = newNode;

    itemCnt += 1;
#if defined(_DEBUG_B_TREE_)
#if _DEBUG_B_TREE_ > 1
    CHECK (CheckTree());
#endif
#endif
    return 1;
}

template <class Node, class T>
void TBPlusTreeBase<Node, T>::DetachNode (
    Node* node,
    TChain& chain)
{
    Node* child = static_cast<Node*> (node->Left() ? node->Left():node->Right());
    Node*& childPtr = static_cast<Node*> (*chain.Pop());
    if (!chain.IsEmpty())
    {
        Node::TNodeBase** parent = chain.Pop();
        (*parent)->Balance() = static_cast<TBalance> ((*parent)->Balance() -
            ((*parent)->Left() == node ? LeftBalance : RightBalance));

        childPtr = child;
        (*parent)->Balance (*parent);
        child = static_cast<Node*> (*parent);
        while (child->Balance() == Balanced && !chain.IsEmpty())
        {
            parent = chain.Pop();
            (*parent)->BalanceDetach (child, *parent);
            child = static_cast<Node*> (*parent);
        }
    }
    else
        childPtr = child;

    itemCnt -= 1;
#if defined(_DEBUG_B_TREE_)
#if _DEBUG_B_TREE_ > 1
    CHECK (CheckTree());
#endif
#endif
}

template <class Node, class T>
Node* TBPlusTreeBase<Node, T>::FindNode (
    const T* t) const
{
#if defined(_DEBUG_B_TREE_)
#if _DEBUG_B_TREE_ > 1
    CHECK (CheckTree());
#endif
#endif
    Node* node = static_cast<Node*> (root);
    while (node)
    {
        if (*node->DataPtr() == *t)
            return node;

        node = static_cast<Node*> (*t < *node->DataPtr() ? node->Left() :
            node->Right());
    }
    return 0;
}

template <class Node, class T>
Node* TBPlusTreeBase<Node, T>::FindNode (
    const T* t,
    TChain& chain)
{
#if defined(_DEBUG_B_TREE_)
#if _DEBUG_B_TREE_ > 1
    CHECK (CheckTree());
#endif
#endif
    Node::TNodeBase** nodePtr = &root;
    Node* node = static_cast<Node*> (*nodePtr);
    while (node)
    {
        chain.Push (nodePtr);
        if (*node->DataPtr() == *t)
            return node;

        nodePtr = (*t < *node->DataPtr() ? &node->Left() : &node->Right());
        node = static_cast<Node*> (*nodePtr);
    }
    return 0;
}

template <class Node, class T>
void TBPlusTreeBase<Node, T>::BalanceAdd (
    TChain& chain)
{
    Node::TNodeBase* child = *chain.Pop();
    do {
        Node::TNodeBase*& node = *chain.Pop();
        if (node->BalanceAdd (child, node))
            break;

        child = node;
    }
    while (child->Balance() && !chain.IsEmpty());
}

#if __DEBUG > 0
#if defined(_DEBUG_B_TREE_)
template <class Node, class T>
int TBPlusTreeBase<Node, T>::CheckTree ()
{
    int height;
    if (root)
    {
        unsigned cnt = root->CheckNode (height);
        CHECK (cnt == itemCnt);
#if _DEBUG_B_TREE_ > 1
        const T* minValue = 0;
        const T* maxValue = 0;
        CheckValues (static_cast<Node&> (*root), minValue, maxValue);
#endif
    }
    return 1;
}

template <class Node, class T>
void TBPlusTreeBase<Node, T>::CheckValues (
    Node& node,
    const T*& minValue,
    const T*& maxValue)
{
    const T* value;
    minValue = maxValue = node.DataPtr();
    if (node.Left())
    {
        CheckValues (static_cast<Node&> (node.LeftNode()), minValue, value);
        CHECK (*value < *node.DataPtr());
    }

    if (node.Right())
    {
        CheckValues (static_cast<Node&> (node.RightNode()), value, maxValue);
        CHECK (*node.DataPtr() < *value);
    }
}
#endif
#endif

/*
 * Template TBPlusTreeIteratorBase, iterator for template TBPlusTreeBase
 */
template <class Node, class T> class TBPlusTreeIteratorBase
{
public:
    TBPlusTreeIteratorBase (const TBPlusTreeBase<Node, T>& t) :
        tree (const_cast<TBPlusTreeBase<Node, T>&> (t))
        {
        first = lowerLimit = upperLimit = 0;
        if (tree.root)
            {
            lowerLimit = tree.root->WalkLeft();
            upperLimit = tree.root->WalkRight();
            first = lowerLimit;
            }
        Restart();
        }

    TBPlusTreeIteratorBase (const TBPlusTreeBase<Node, T>& t, const T* start,
        const T* end) :
        tree (const_cast<TBPlusTreeBase<Node, T>&> (t))
        {
        Restart (start, end);
        }

    operator int () const
        {
        return !chain.IsEmpty();
        }

    const T* Current (void) const
        {
        PRECONDITION (!chain.IsEmpty());
        return GetCurrent();
        }

    const T* operator ++ (int)
        {
        const T* t = Current();
        Next();
        return t;
        }

    const T* operator ++ ()
        {
        Next();
        return Current();
        }

    const T* operator -- (int)
        {
        const T* t = Current();
        Previous();
        return t;
        }

    const T* operator -- ()
        {
        Previous();
        return Current();
        }

    void Restart (void);
    void Restart (const T*, const T*);

private:
    T* GetCurrent (void) const
        {
        return static_cast<Node&> (**chain.Top()).DataPtr();
        }

    void Next (void);
    void Previous (void);
    void FindLimitNode (const T&, int);

    typedef TBPlusTreeBase<Node, T> Tree;

    Tree& tree;
    Tree::TChain chain;
    const Node::TNodeBase* first;
    const Node::TNodeBase* lowerLimit;
    const Node::TNodeBase* upperLimit;
}

/*
 * Member functions for class TBPlusTreeIteratorBase
 */
template <class Node, class T>
void TBPlusTreeIteratorBase<Node, T>::Restart (void)
{
    chain.Flush (TShouldDelete::NoDelete);
    if (lowerLimit && upperLimit)
        tree.FindNode (static_cast<const Node&> (*first).DataPtr(), chain);
}

template <class Node, class T>
void TBPlusTreeIteratorBase<Node, T>::Restart (
    const T* start,
    const T* end)
{
    chain.Flush (TShouldDelete::NoDelete);
    first = lowerLimit = upperLimit = 0;
    if (!tree.root)
        return;

    int direction = start && end ? *start < *end : 1;
    if (start)
        FindLimitNode (*start, 0 ^ direction);
    else
    {
        chain.Push (&tree.root);
        tree.root->WalkLeft (chain);
    }

    if (!chain.IsEmpty())
        lowerLimit = *chain.Top();

    first = lowerLimit;
    chain.Flush (TShouldDelete::NoDelete);
    if (end)
        FindLimitNode (*end, !direction);
    else
    {
        chain.Push (&tree.root);
        tree.root->WalkRight (chain);
    }

    if (!chain.IsEmpty())
        upperLimit = *chain.Top();

    if (!direction)
    {
        const Node::TNodeBase* t = upperLimit;
        upperLimit = lowerLimit;
        lowerLimit = t;
    }
    Restart();
}

template <class Node, class T>
void TBPlusTreeIteratorBase<Node, T>::FindLimitNode (
    const T& t,
    int direction)
{
    if (tree.FindNode (&t, chain) == 0 && ((t < *GetCurrent()) ^ direction))
        if (direction)
            Next();
        else
            Previous();
}

template <class Node, class T>
void TBPlusTreeIteratorBase<Node, T>::Next (void)
{
    if (chain.IsEmpty() || *chain.Top() == upperLimit)
        chain.Flush (TShouldDelete::NoDelete);
    else
        Node::Next (chain);
}

template <class Node, class T>
void TBPlusTreeIteratorBase<Node, T>::Previous (void)
{
    if (chain.IsEmpty() || *chain.Top() == lowerLimit)
        chain.Flush (TShouldDelete::NoDelete);
    else
        Node::Previous (chain);
}

/*
 * Template TBPlusTreeImp. Direct tree
 */
template <class Node, class T> class TBPlusTreeImp :
    public TBPlusTreeBase<Node, T>
{
    typedef TBPlusTreeBase <Node, T> Parent;

public:
    TBPlusTreeImp (void) : TBPlusTreeBase<Node, T>()
        {
        }

    ~TBPlusTreeImp (void)
        {
        Flush();
        chain.Flush (TShouldDelete::NoDelete);
        }

    int HasMember (const T& t) const
        {
        return Parent::HasMember (&t);
        }

    int Destroy (const T& t)
        {
        return Detach (t);
        }

    int DestroyLast (void)
        {
        return DetachLast();
        }

    int DestroyFirst (void)
        {
        return DetachFirst();
        }

    T* Find (const T& t) const
        {
        return Parent::Find (&t);
        }

    void Flush (void)
        {
        DestroyAllNodes (static_cast<Node*> (root));
        Parent::Flush();
        }

    int Add (const T&);
    int Detach (const T&);
    int DetachLast (void);
    int DetachFirst (void);

private:
    void Detach (Node*, TChain&);
    void DestroyAllNodes (Node*) const;

    TChain chain;
};

/*
 * Member function for template TBPlusTreeImp
 */
template <class Node, class T>
int TBPlusTreeImp<Node, T>::Add (
    const T& t)
{
    chain.Flush (TShouldDelete::NoDelete);
    if (FindNode (&t, chain))
        return 0;

    return AddNode (new Node (t), chain);
}

template <class Node, class T>
int TBPlusTreeImp<Node, T>::Detach (
    const T& t)
{
    chain.Flush (TShouldDelete::NoDelete);
    Node* node = FindNode (&t, chain);
    if (!node)
        return 0;

    Detach (node, chain);
    return 1;
}

template <class Node, class T>
int TBPlusTreeImp<Node, T>::DetachLast (void)
{
    if (!root)
        return 0;

    chain.Flush (TShouldDelete::NoDelete);
    Node* node = static_cast<Node*> (root->WalkRight (chain));
    Detach (node, chain);
    return 1;
}

template <class Node, class T>
int TBPlusTreeImp<Node, T>::DetachFirst (void)
{
    if (!root)
        return 0;

    chain.Flush (TShouldDelete::NoDelete);
    Node* node = static_cast<Node*> (root->WalkLeft (chain));
    Detach (node, chain);
    return 1;
}

template <class Node, class T>
void TBPlusTreeImp<Node, T>::Detach (
    Node* node,
    TChain& chain)
{
#if defined(_DEBUG_B_TREE_)
    CHECK (CheckTree());
#endif

    if (node->Left() && node->Right())
    {
        Node* remove;
        if (node->Balance() == RightBalance)
        {
            chain.Push (&node->Right());
            remove = static_cast<Node*> (node->RightNode().WalkLeft (chain));
        }
        else
        {
            chain.Push (&node->Left());
            remove = static_cast<Node*> (node->LeftNode().WalkRight (chain));
        }

        node->Data() = remove->Data();
        node = remove;
    }

    DetachNode (node, chain);
    delete node;
}

template <class Node, class T>
void TBPlusTreeImp<Node, T>::DestroyAllNodes (
    Node* node) const
{
    if (node)
    {
        DestroyAllNodes (static_cast<Node*> (node->Left()));
        DestroyAllNodes (static_cast<Node*> (node->Right()));
        delete node;
    }
}

/*
 * Template TBPlusTreeIteratorImp, iterator for template TBPlusTreeImp
 */
template <class Node, class T> class TBPlusTreeIteratorImp :
    public TBPlusTreeIteratorBase<Node, T>
{
    typedef TBPlusTreeIteratorBase<Node, T> Parent;

    public:
    TBPlusTreeIteratorImp (const TBPlusTreeImp<Node, T>& t) :
        TBPlusTreeIteratorBase<Node, T> (t)
        {
        }

    TBPlusTreeIteratorImp (const TBPlusTreeImp<Node, T>& t, const T& start,
        const T& end) : TBPlusTreeIteratorBase<Node, T> (t, &start, &end)
        {
        }

    void Restart (void)
        {
        Parent::Restart();
        }

    void Restart (const T& start, const T& end)
        {
        Parent::Restart (&start, &end);
        }

    const T& operator ++ (int i)
        {
        return *Parent::operator ++ (i);
        }

    const T& operator ++ ()
        {
        return *Parent::operator ++ ();
        }

    const T& operator -- (int i)
        {
        return *Parent::operator -- (i);
        }

    const T& operator -- ()
        {
        return *Parent::operator -- ();
        }
};

/*
 * Template TIBPlusTreeImp. Indirect tree
 */
template <class Node, class T> class TIBPlusTreeImp :
    public TBPlusTreeBase<Node, T>, public TShouldDelete
{
    typedef TBPlusTreeBase <Node, T> Parent;

public:
    TIBPlusTreeImp (void) : TBPlusTreeBase<Node, T>()
        {
        }

    ~TIBPlusTreeImp (void)
        {
        Flush();
        chain.Flush (TShouldDelete::NoDelete);
        }

    int Destroy (T* t)
        {
        return Detach (t, Delete);
        }

    int DestroyLast (void)
        {
        return DetachLast (Delete);
        }

    int DestroyFirst (void)
        {
        return DetachFirst (Delete);
        }

    void Flush (DeleteType dt = DefDelete)
        {
        DestroyAllNodes (static_cast<Node*> (root), DelObj (dt));
        Parent::Flush();
        }

    int Add (T*);
    int Detach (T*, DeleteType = NoDelete);
    int DetachLast (DeleteType = NoDelete);
    int DetachFirst (DeleteType = NoDelete);

private:
    void Detach (Node*, TChain&, int);
    void DestroyAllNodes (Node*, int) const;

    TChain chain;
};

/*
 * Member function for template TIBPlusTreeImp
 */
template <class Node, class T>
int TIBPlusTreeImp<Node, T>::Add (
    T* t)
{
    chain.Flush (TShouldDelete::NoDelete);
    if (FindNode (t, chain))
        return 0;

    return AddNode (new Node (t), chain);
}

template <class Node, class T>
int TIBPlusTreeImp<Node, T>::Detach (
    T* t,
    DeleteType dt)
{
    chain.Flush (TShouldDelete::NoDelete);
    Node* node = FindNode (t, chain);
    if (!node)
        return 0;

    Detach (node, chain, DelObj (dt));
    return 1;
}

template <class Node, class T>
int TIBPlusTreeImp<Node, T>::DetachLast (
    DeleteType dt)
{
    if (!root)
        return 0;

    chain.Flush (TShouldDelete::NoDelete);
    Node* node = static_cast<Node*> (root->WalkRight (chain));
    Detach (node, chain, DelObj (dt));
    return 1;
}

template <class Node, class T>
int TIBPlusTreeImp<Node, T>::DetachFirst (
    DeleteType dt)
{
    if (!root)
        return 0;

    chain.Flush (TShouldDelete::NoDelete);
    Node* node = static_cast<Node*> (root->WalkLeft (chain));
    Detach (node, chain, DelObj (dt));
    return 1;
}

template <class Node, class T>
void TIBPlusTreeImp<Node, T>::Detach (
    Node* node,
    TChain& chain,
    int delObj)
{
#if defined(_DEBUG_B_TREE_)
    CHECK (CheckTree());
#endif

    if (delObj)
        delete node->Data();

    if (node->Left() && node->Right())
    {
        Node* remove;
        if (node->Balance() == RightBalance)
        {
            chain.Push (&node->Right());
            remove = static_cast<Node*> (node->RightNode().WalkLeft (chain));
        }
        else
        {
            chain.Push (&node->Left());
            remove = static_cast<Node*> (node->LeftNode().WalkRight (chain));
        }

        node->Data() = remove->Data();
        node = remove;
    }

    DetachNode (node, chain);
    delete node;
}

template <class Node, class T>
void TIBPlusTreeImp<Node, T>::DestroyAllNodes (
    Node* node,
    int delObj) const
{
    if (node)
    {
        DestroyAllNodes (static_cast<Node*> (node->Left()), delObj);
        DestroyAllNodes (static_cast<Node*> (node->Right()), delObj);
        if (delObj)
            delete node->Data();

        delete node;
    }
}

/*
 * Template TIBPlusTreeIteratorImp, iterator for template TIBPlusTreeImp
 */
template <class Node, class T> class TIBPlusTreeIteratorImp :
    public TBPlusTreeIteratorBase<Node, T>
{
public:
    TIBPlusTreeIteratorImp (const TIBPlusTreeImp<Node, T>& t) :
        TBPlusTreeIteratorBase<Node, T> (t)
        {
        }

    TIBPlusTreeIteratorImp (const TIBPlusTreeImp<Node, T>& t, const T* start,
        const T* end) : TBPlusTreeIteratorBase<Node, T> (t, start, end)
        {
        }
};

/*
 * Template TBPlusTree. Direct tree with allocator
 */
template <class T, class Alloc> class TMBPlusTree :
    public TBPlusTreeImp<TDNode<T, Alloc>, T>
{
public:
    TMBPlusTree (void)
        {
        }
};

/*
 * Template TMBPlusTreeIterator, iterator for template TMBPlusTree
 */
template <class T, class Alloc> class TMBPlusTreeIterator :
    public TBPlusTreeIteratorImp<TDNode<T, Alloc>, T>
{
public:
    TMBPlusTreeIterator (const TMBPlusTree<T, Alloc>& t) :
        TBPlusTreeIteratorImp<TDNode<T, Alloc>, T> (t)
        {
        }

    TMBPlusTreeIterator (const TMBPlusTree<T, Alloc>& t, const T& start, const T& end) :
        TBPlusTreeIteratorImp<TDNode<T, Alloc>, T> (t, start, end)
        {
        }
};

/*
 * Template TIBPlusTree. Indirect tree with allocator
 */
template <class T, class Alloc> class TMIBPlusTree :
    public TIBPlusTreeImp<TINode<T, Alloc>, T>
{
public:
    TMIBPlusTree (void)
        {
        }
};

/*
 * Template TIBPlusTreeIterator, iterator for template TIBPlusTree
 */
template <class T, class Alloc> class TMIBPlusTreeIterator :
    public TIBPlusTreeIteratorImp<TINode<T, Alloc>, T>
{
public:
    TMIBPlusTreeIterator (const TMIBPlusTree<T, Alloc>& t) :
        TIBPlusTreeIteratorImp<TINode<T, Alloc>, T> (t)
        {
        }

    TMIBPlusTreeIterator (const TMIBPlusTree<T, Alloc>& t, const T* start,
        const T* end) :
        TIBPlusTreeIteratorImp<TINode<T, Alloc>, T> (t, start, end)
        {
        }
};

/*
 * Template TBPlusTree. Direct tree
 */
template <class T> class TBPlusTree :
    public TMBPlusTree<T, TStandardAllocator>
{
public:
    TBPlusTree (void)
        {
        }
};

/*
 * Template TBPlusTreeIterator, iterator for template TBPlusTree
 */
template <class T> class TBPlusTreeIterator :
    public TMBPlusTreeIterator<T, TStandardAllocator>
{
public:
    TBPlusTreeIterator (const TBPlusTree<T>& t) :
        TMBPlusTreeIterator<T, TStandardAllocator> (t)
        {
        }

    TBPlusTreeIterator (const TBPlusTree<T>& t, const T& start, const T& end) :
        TMBPlusTreeIterator<T, TStandardAllocator> (t, start, end)
        {
        }
};

/*
 * Template TIBPlusTree. Indirect tree
 */
template <class T> class TIBPlusTree :
    public TMIBPlusTree<T, TStandardAllocator>
{
public:
    TIBPlusTree (void)
        {
        }
};

/*
 * Template TIBPlusTreeIterator, iterator for template TIBPlusTree
 */
template <class T> class TIBPlusTreeIterator :
    public TMIBPlusTreeIterator<T, TStandardAllocator>
{
public:
    TIBPlusTreeIterator (const TIBPlusTree<T>& t) :
        TMIBPlusTreeIterator<T, TStandardAllocator> (t)
        {
        }

    TIBPlusTreeIterator (const TIBPlusTree<T>& t, const T* start,
        const T* end) :
        TMIBPlusTreeIterator<T, TStandardAllocator> (t, start, end)
        {
        }
};
#endif